import java.util.*;

/**
 * 赫夫曼解码
 *
 * @Author: wanqian
 * @Date: 2021/2/9 15:12
 */
public class HuffmanDecodeDemo {

    public static String content = "i like like like java do you like a java";

    public static void main(String[] args) {
        byte[] bytes = HuffmanEncodeDemo.huffmanZip(content.getBytes());
        Map<Byte, String> huffCodeTable = HuffmanEncodeDemo.getHuffCodeTable(content);
        String decode = decode(huffCodeTable, bytes);
        System.out.println(decode);
    }

    /**
     * 赫夫曼解码
     *
     * @param huffCodeTable 编码表
     * @param huffmanBytes  经过编码的字节数组
     * @return
     */
    public static String decode(Map<Byte, String> huffCodeTable, byte[] huffmanBytes) {

        StringBuilder stringBuilder = new StringBuilder();
        //取出最后一个byte的有效位数
        int lastByteLength = huffmanBytes[huffmanBytes.length - 1];
        //逐个将字节转换成二进制字符串
        for (int i = 0; i < huffmanBytes.length - 1; i++) {
            //8位的二进制字符串
            String bitString = byteToBitString(huffmanBytes[i]);
            //若为最后一个字节则截取有效数
            if (i == huffmanBytes.length - 2) {
                bitString = bitString.substring(bitString.length() - lastByteLength);
            }
            stringBuilder.append(bitString);
        }

        //字节数组还原成的二进制字符串
        String binaryCodeString = stringBuilder.toString();

        stringBuilder.setLength(0);
        Set<Map.Entry<Byte, String>> entries = huffCodeTable.entrySet();
        int start = 0;
        //从头开始根据编码表进行匹配
        while (start < binaryCodeString.length()) {
            //截取掉已经匹配的部分
            String substring = binaryCodeString.substring(start);
            //根据8位二进制字符串匹配对应的字符
            Optional<Map.Entry<Byte, String>> first =
                    entries.parallelStream().filter(entry -> substring.startsWith(entry.getValue()))
                            .findFirst();

            if (first.isPresent()) {
                Map.Entry<Byte, String> entry = first.get();
                //根据二进制字符串长度，调整匹配开始位置
                start += entry.getValue().length();
                stringBuilder.append((char) entry.getKey().byteValue());
            } else {
                break;
            }
        }
        return stringBuilder.toString();
    }

    public static List<Byte> decodeByte(Map<Byte, String> huffCodeTable, byte[] huffmanBytes) {

        StringBuilder stringBuilder = new StringBuilder();
        //取出最后一个byte的有效位数
        int lastByteLength = huffmanBytes[huffmanBytes.length - 1];
        //逐个将字节转换成二进制字符串
        for (int i = 0; i < huffmanBytes.length - 1; i++) {
            //8位的二进制字符串
            String bitString = byteToBitString(huffmanBytes[i]);
            //若为最后一个字节则截取有效数
            if (i == huffmanBytes.length - 2) {
                bitString = bitString.substring(bitString.length() - lastByteLength);
            }
            stringBuilder.append(bitString);
        }

        //字节数组还原成的二进制字符串
        String binaryCodeString = stringBuilder.toString();

        ArrayList<Byte> bytes = new ArrayList<>();
        Set<Map.Entry<Byte, String>> entries = huffCodeTable.entrySet();
        int start = 0;
        //从头开始根据编码表进行匹配
        while (start < binaryCodeString.length()) {
            //截取掉已经匹配的部分
            String substring = binaryCodeString.substring(start);
            //根据8位二进制字符串匹配对应的字符
            Optional<Map.Entry<Byte, String>> first =
                    entries.parallelStream().filter(entry -> substring.startsWith(entry.getValue()))
                            .findFirst();

            if (first.isPresent()) {
                Map.Entry<Byte, String> entry = first.get();
                //根据二进制字符串长度，调整匹配开始位置
                start += entry.getValue().length();
                bytes.add(entry.getKey());
            } else {
                break;
            }
        }
        return bytes;
    }

    /**
     * 将字节转换成二进制字符串
     *
     * @param b
     * @return
     */
    public static String byteToBitString(byte b) {
        //byte->int 最高位是0则前面补0，是1则补1
        int temp = b;
        //保留后八位(如果是正数前面的0将被自动忽略)
        temp |= 0x100;
        //转换成二进制数的字符串，然后截取后八位
        String binaryString = Integer.toBinaryString(temp);
        return binaryString.substring(binaryString.length() - 8);
    }
}
